package longestPalindrome;
/**
 * @Date 2020/03/27
 * @author 王光浩
 * @Thinking 使用双指针
 * @Analysis 时间复杂度O（n^3）-最差的时间复杂度仍然没有变，空间复杂度O（n）
 */
public class MyMethodTwo {
	public String longestPalindrome(String s) {
		StringBuilder ret=new StringBuilder();
		int first=0;
		//获取最长回文子串（最长回文子串的范围在 first -  (first+ret.length()+1,s.length-1)之间）
		while((first+ret.length())<s.length()) {
			int second=s.length()-1;
			while(second>=(first+ret.length())) {
				if(!helper(s,ret,first,second--))break;
			}
			first+=1;
		}
		return ret.toString();
	}
	private boolean helper(String s,StringBuilder ret,int first,int second) {
		int pre=first;
		int last=second;
		//判断是否是回文字符串
		while(pre<last) {
			if((s.charAt(pre++)^s.charAt(last--))!=0)return false;
		}
		ret.setLength(0);
		ret.append(s.substring(first,second+1));
		return true;
	}
}
